//
//  Problem540.swift
//  TestProject
//
//  Created by 武侠 on 2021/5/18.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 540. 有序数组中的单一元素
 给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。

 示例 1:
     输入: [1,1,2,3,3,4,4,8,8]
     输出: 2
 示例 2:
     输入: [3,3,7,7,10,11,11]
     输出: 10
    注意: 您的方案应该在 O(log n)时间复杂度和 O(1)空间复杂度中运行。
 */
@objcMembers class Problem540: NSObject {
    func solution() {
        print(singleNonDuplicate([1,1,2,3,3,4,4,8,8]))
        print(singleNonDuplicate([3,3,7,7,10,11,11]))
        print(singleNonDuplicate([1]))
        print(singleNonDuplicate([1,1,2]))
        print(singleNonDuplicate([1,2,2]))
    }
    
    /*
     二分法：
     1: 使用二分法进行分割，计算mid
     2: 如果n[mid] == n[mid+1], 那么在mid和mid+1进行切割,分成左部分和右部分，单个个数肯定在奇数个里面，这时有2种情况：
        n[mid] = 3,
        1 1 2    3 3   4 4 5 5      在左边
        1 1 2 2  3 3   4 5 5        在右边
        如果n[mid] == n[mid-1],那么mid -= 1，然后执行上面的操作
        
     */
    func singleNonDuplicate(_ nums: [Int]) -> Int {
        if nums.count == 1 {
            return nums[0]
        }
        var left : Int = 0
        var right: Int = nums.count-1
        var mid = 0
        while left <= right {
            mid = (left + right) / 2
            
            if mid > 0, nums[mid] == nums[mid - 1]{
                mid -= 1
            } else if mid == nums.count-1 || nums[mid] != nums[mid + 1] {
                return nums[mid]
            }
            
            if (mid - left) % 2 == 0 {  // 左边是偶数，单个在右边
                left = mid + 2
            } else {
                right = mid - 1
            }
        }
        
        return left
    }
}
